package com.zlk.algorithm.algorithm.dynamicPlan.twoDimension;

// 最长回文子序列
// 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度
// 测试链接 : https://leetcode.cn/problems/longest-palindromic-subsequence/
public class Code04_LongestPalindromicSubsequence {


    public int longestPalindromeSubseq(String s) {
       // return f2(s.toCharArray(),0,s.length()-1);
        int[][] dp = new int[s.length()][s.length()];
//        return f3(s.toCharArray(),0,s.length()-1,dp);
//        return f4(s.toCharArray());
        return f5(s);
    }

    /**
     * 动态规划+空间压缩版本
     * @param s
     * @return
     */
    private int f5(String text) {
        char[] s = text.toCharArray();
        int len = s.length;
        int[] dp =new int[len+1];
        int lLen = len;
        int rLen = len;
        for (int i = lLen-1; i >=0; i--) {
            int downLeft = 0;
            for (int j = i; j < rLen; j++) {
                if(j==i){
                    dp[j] = 1;
                }else{
                    int temp = dp[j];
                    if(s[i]==s[j]){
                        dp[j] = downLeft+2;
                    }else{
                        dp[j] = Math.max(dp[j],dp[j-1]);
                    }
                    downLeft = temp;

                }
            }
        }
        return dp[rLen-1];
    }


    /**
     * 区间dp
     * @param s
     * @return
     */
    private int f4(char[] s) {

        int len = s.length;
        int[][] dp =new int[len+1][len];
        int lLen = len;
        int rLen = len;
        for (int i = lLen-1; i >=0; i--) {
            for (int j = i; j < rLen; j++) {
                if(j==i){
                    dp[i][j] = 1;
                }else{
                    if(s[i]==s[j]){
                        dp[i][j] = dp[i+1][j-1]+2;
                    }else{
                        dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                    }
                }
            }
        }
        return dp[0][rLen-1];
    }

    private int f3(char[] s, int l, int r, int[][] dp) {
        if(l>r){
            return 0;
        }
        if(l==r){
            return 1;
        }
        if(dp[l][r]!=0){
            return dp[l][r];
        }
        if(s[l]==s[r]){
            dp[l][r] = f3(s,l+1,r-1,dp)+2;
            return dp[l][r];
        }else{
            dp[l][r] = Math.max(f3(s,l+1,r,dp),f3(s,l,r-1,dp));
            return dp[l][r];
        }
    }

    /**
     * 可能性分析
     * 1、s[l] = s[r] ，/   s[l+1]    s[r-1]  +1
     * 2、 S[l] !=S【r】   /  s[l+1]  s[r]  or  s[l]  s[r-1]
     * @param s
     * @param l
     * @param r
     * @return
     */
    private int f2(char[] s, int l, int r) {
        if(l>r){
            return 0;
        }
        if(l==r){
            return 1;
        }
        if(s[l]==s[r]){
             return f2(s,l+1,r-1)+2;
        }else{
             return Math.max(f2(s,l+1,r),f2(s,l,r-1));
        }
    }

    private int f1(String s) {
        String reverse = "";
        for (int i = s.length()-1; i >=0; i--) {
            reverse+=s.charAt(i);
        }

        char[] s1 = s.toCharArray();
        char[] s2 = reverse.toCharArray();
        int n = s1.length;
        int m = s2.length;
        int[][] dp = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if(s1[i-1]==s2[j-1]){
                    dp[i][j] = dp [i-1][j-1] +1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }


}
